package william.mergesort;

/**
 * @author ZhangShenao
 * @date 2024/1/26
 * @description <a href="https://leetcode.cn/problems/reverse-pairs/description/">...</a>
 */
public class Leetcode493_翻转对 {
    /**
     * 采用归并排序的思想，指针向前移动不回退。
     * 在 merge 的过程中，针对左组中的每个元素，在右组中维护一个 [M+1,windowR) 区间 ，在该区间内，右组中的每个元素的2倍，均小于左组中当前元素。记录并累计翻转对的数量。
     * 记录 [M+1,windowR) 区间 ，并将 windowR 指针持续向右推进，直到整个左组或右组中无元素。
     * 再从头开始进行 merge 操作，将两个有序数组合并成一个整体有序数组。
     * 返回当前区间内累计的翻转对的数量。
     */
    public int reversePairs(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return 0;
        }

        //调用递归实现
        return reversePairsRecursion(nums, 0, nums.length - 1);

    }

    /**
     * 递归实现
     * 将数组nums[L,R]范围内处理成有序,并返回该区间内翻转对的数量
     */
    private int reversePairsRecursion(int[] nums, int L, int R) {
        //递归终止条件
        if (L == R) {
            return 0;
        }

        //找到数组中点,将整个数组分成左、右两个部分
        int M = L + ((R - L) >> 1);

        //递归调用,将左、右两部分数组依次处理成有序,并获取两个数字的翻转对数量
        int lCount = reversePairsRecursion(nums, L, M);
        int rCount = reversePairsRecursion(nums, M + 1, R);

        //将左、右两个有序数组,合并成一个整体有序数组,并在合并过程中计算翻转对数量
        int mCount = merge(nums, L, M, R);

        //最终反转对总数=左数组翻转对数量+右数组翻转对数量+合并过程中计算得出的翻转对数量
        return lCount + rCount + mCount;
    }

    /**
     * 合并操作
     * 将nums[L,M]和nums[M+1,R]两个有序数组,合并成一个整体有序数组,并返回翻转对的数量
     */
    private int merge(int[] nums, int L, int M, int R) {
        //维护[M+1,windowR)区间,该区间内的所有元素的2倍均<左数组当前元素
        //将windowR区间持续向右推进
        int count = 0;
        int windowR = M + 1;

        for (int l = L; l <= M; l++) {
            while (windowR <= R && (long) nums[l] > (long) nums[windowR] * 2) { //强制转换成long型,避免溢出
                ++windowR;
            }
            //[4,6] [1,3] l=0 M=1 windowR=3 count=windowR-M-1=3-1-1=1
            //针对当前左组元素nums[l],产生的翻转对总数=windowR-1-(M+1)+1=windowR-M-1
            //累加翻转对数量
            count += (windowR - M - 1);
        }

        //进行merge操作,将两个有序数组,合并成一个整体有序数组
        int l = L;
        int r = M + 1;
        int i = 0;
        int len = R - L + 1;
        int[] tmp = new int[len];
        while (l <= M && r <= R) {
            if (nums[l] < nums[r]) {
                tmp[i++] = nums[l++];
            } else {
                tmp[i++] = nums[r++];
            }
        }

        while (l <= M) {
            tmp[i++] = nums[l++];
        }
        while (r <= R) {
            tmp[i++] = nums[r++];
        }
        for (i = 0; i < len; i++) {
            nums[L + i] = tmp[i];
        }

        //返回翻转对总数
        return count;
    }
}
